#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int fa[1010];

    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    void merge(int x, int y) {
        fa[find(x)] = find(y);
    }

    // 平均时间复杂度为 O(nα(n))，其中 α(n) < 5
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
        }

        int j = -1;
        for (int i = 0; i < n; ++i) {
            int x = edges[i][0];
            int y = edges[i][1];

            // 如果原来这两个点已经连通，则证明新的这条边是冗余的
            if (find(x) == find(y)) {
                j = i;
            } else {
                // 否则将这两个点连通
                merge(x, y);
            }
        }

        return edges[j];
    }
};